package num260;

/**
 * 260. 只出现一次的数字 III
 * 题目：https://leetcode-cn.com/problems/single-number-iii/
 * 三叶姐题解: https://leetcode-cn.com/problems/single-number-iii/solution/gong-shui-san-xie-yi-ti-shuang-jie-ha-xi-zgi4/
 * <p>
 * 异或
 */
class Solution2 {
    public int[] singleNumber(int[] nums) {
        int sum = 0;
        for (int i : nums) {
            sum ^= i;
        }
        int k = -1;
        for (int i = 31; i >= 0 && k == -1; i--) {
            if ((sum >>> i & 1) == 1) k = i;
        }
        int[] ans = new int[2];
        for (int i : nums) {
            if ((i >>> k & 1) == 1) ans[0] ^= i;
            else ans[1] ^= i;
        }
        return ans;
    }

    public static void main(String[] args) {
        new Solution2().singleNumber(new int[]{0, 1, 1, 2});
    }
}
